1. Field
The disclosed teachings relate to routing, and more particularly, to a technique for routing which is capable of discovering an optimal route by use of a backoff scheme. A backoff for the backoff scheme is calculated based on a route cost such as link quality.
2. Description of the Related Art
An on-demand routing such as Ad hoc On Demand Distance Vector (AODV) routing is to discover a route effectively in an Ad hoc type wireless network. In AODV routing, when a source node wishes to send data to a destination node but contains no effective routing information, the source node floods the whole network with a Route REQest (RREQ) packet to discover possible routes leading to the destination node. In order to limit route discovery traffic, each intermediate node only rebroadcasts the first received RREQ packet and discards duplicated RREQ packets arriving subsequent to the first RREQ packet. Such an AODV routing is more suitable to a hop-count-based routing and guarantees the discovery of the shortest route.
However, the first received RREQ packet is not necessarily essential in discovering the optimal route in view of route cost. That is, in wireless networks, the hop-count is not the dominant route cost criterion any longer. Instead, link quality, energy efficiency, and security become the key factors to determine the route cost. In other words, the AODV routing is unsuitable to a cost-based routing which prefers the optimal route to the shortest route. This is because if the intermediate node only relays the first RREQ packet, the best route is very likely ignored.
FIG. 1 illustrates a network by way of an example, in which S denotes a source node and D denotes a destination node. Node F receives a first RREQ packet through route S-B-F, which is the shortest route between the node S and the node F. However, since the node B is located at transmission borders 10 and 20 of both the nodes S and F, link qualities in the routes S-B and B-F are very poor. Although the route S-C-E-F guarantees higher link quality, the RREQ packets transmitted through this route are discarded by the node F as the duplicated RREQ packets. Accordingly, the node S does not know the existence of the route S-C-E-F-G-D which is the optimal route in view of link qualities.
If all of the intermediate nodes are allowed to relay the duplicated RREQ packets, the probability that the optimal route is discovered increases. However, if most intermediate nodes have to rebroadcast the same RREQ packets for multiple times, control overhead inevitably increases. Accordingly, since all of the intermediate nodes relay the duplicated packets, the precious resources of wireless devices are depleted and normal data traffic is interfered with.